P1064 金明的预算方案

存在依赖关系背包转化分组背包。

题意

给定 $n$ 个物品的价值和体积，他们之间存在简单的依赖关系，即一个结点要么是父亲结点，要么是儿子结点，且一个父亲结点最多有两个儿子结点。

[USACO12OPEN]Bookshelf G

题意

考虑现在有 $n$ 本书并给定一个最大长度 $L$，第 $i$ 本书有高度 $h_i,w_i$。每次选取一段范围满足该段范围内的所有书的 $\sum w_i\leq L$，那么这次选取的贡献为 $\max\{h_i\}$。

Railgun

题意

给定 $n,a,b$，你现在在 $0$ 处跳格子，每次可以向前跳 $a$ 格或者 $b$ 格。

求到达 $n$ 格的方案数，答案对 $10,007$ 取模。$(n,a,b\in[1,10^9])$

CF1305G-Kuroni and Antihype

给定的数据范围是一个弱化版本。

题意

给定 $n$ 个点权 $\{a\}$，并按照规则：对于 $i,j$，如果 $i \& j=0$ 则对 $i,j$ 连边，生成图 $G$。

现在要求 $G$ 中的每个点都要按照如下规则加入集合 $S$：

1. 直接将点 $i$ 加入集合 $S$，贡献为 0；
2. 如果集合中已经存在点 $j$ 且点 $i,j$ 之间存在连边，那么将 $i$ 加入集合 $S$，贡献为 $a_i$。

求最大贡献，$n\leq 2\times10^3,a_i\leq10^9$。

CF1375G-Tree Modification

题意

给定一棵有 $n$ 个结点的树，每次操作选取 3 个点 $i,j,k$ 满足 $i,j$ 存在连边，$j,k$ 存在连边，定义一次操作为：

1. 将 $i$ 的所有出边删除。
2. 将原先除去 $j$ 外与 $i$ 存在连边的点与 $k$ 连边。
3. 连接 $i,k$ 两点。

求最小的操作次数使得树存在度为 $n-1$ 的点。

Teleport

题意

给定一个长度为 $n$ 的序列 $\{a\}$，$q$ 次询问。每次查询区间 $[l,r]$，若能选出 1 个三元组 $(a_i,a_j,a_k)$ 使得能够构成三角形，输出 Triangle，否则输出 Not triangle。注意 $i\ne j,j\ne k$，$n\leq 2\times 10^5,a_i\leq10^9$。

Electro Master

上午唯一写出的题。

题意

给定 $n$ 个矩形，值域范围 $r\times c$，求有被至少 $n-1$ 个矩形覆盖的位置数目。

洛谷-P3198 [HNOI2008]遥远的行星

题意

现在给定一个序列 $\{a\}$，令 $f(i,j)=\frac{a_i \times a_j}{j-i}$。对于每个 $i$，计算出所有满足 $j\leq i \times k$ 的 $f(i,j)$，（其中 $k$ 为一个小于 $0.35$ 的常量），相对误差小于 $5\%$。

ATCoder-[ABC176F] Brave CHAIN

题好我非，交了 14 遍才过，一直 RE，原因是储存修改的数组开小了，然而以为是在调用存值的时候数组越界，从下午调到晚上。

ATCoder-[ABC179F] Simplified Reversi

周末的赛题，然而考场上因为 E 题的一点细节没处理好，只剩下 30 min 来写 F，想到了做法后索性就没写 Code 了。